{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.8.1-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python38164bitbed07143d37b49c8ba24bbf4d83c1753",
   "display_name": "Python 3.8.1 64-bit"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。\n",
    "\n",
    "形式上，如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。\n",
    "\n",
    " \n",
    "\n",
    "示例 1：\n",
    "\n",
    "输出：[0,2,1,-6,6,-7,9,1,2,0,1]\n",
    "输出：true\n",
    "解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "class Solution:\n",
    "\n",
    "    def canThreePartsEqualSum(self, A: List[int]) -> bool:\n",
    "        n = len(A)\n",
    "        if n < 3:\n",
    "            return False\n",
    "        s = sum(A)\n",
    "        if s % 3 != 0:\n",
    "            return False\n",
    "        part_one = 0\n",
    "        for i in range(0, n-2):\n",
    "            part_one += A[i]\n",
    "            for j in range(i+1, n-1):\n",
    "                # print(part_one, A[i+1:j+1], s-part_one)\n",
    "                part_two = sum(A[i+1:j+1])\n",
    "                part_three = s - part_one - part_two\n",
    "                if part_one == part_two == part_three:\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "# 改了一边还超时"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "看了下解题思路终于过了，这还是简单题？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "还是双指针，如果第一部分的和不为`sum(A)/3` 就继续加， 同理：第二部分的和不为"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "\n",
    "    def canThreePartsEqualSum(self, A: List[int]) -> bool:\n",
    "        n = len(A)\n",
    "        if n < 3:\n",
    "            return False\n",
    "        s = sum(A)\n",
    "        if s % 3 != 0:\n",
    "            return False\n",
    "        mid = s / 3\n",
    "        part_one = 0\n",
    "        for i in range(0, n-2):\n",
    "            part_one += A[i]\n",
    "            if part_one != mid:\n",
    "                continue\n",
    "            part_two = 0\n",
    "            for j in range(i+1, n-1):\n",
    "                part_two += A[j]\n",
    "                if part_two != mid:\n",
    "                    continue\n",
    "                part_three = s - part_one - part_two\n",
    "                if part_two == part_three:\n",
    "                    return True\n",
    "        return False\n",
    "\n"
   ]
  }
 ]
}